# 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 
# O(n) 并且只使用常数级别额外空间的解决方案。
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：nums = [1,2,0]
# 输出：3
# 解释：范围 [1,2] 中的数字都在数组中。 
# 
#  示例 2： 
# 
#  
# 输入：nums = [3,4,-1,1]
# 输出：2
# 解释：1 在数组中，但 2 没有。 
# 
#  示例 3： 
# 
#  
# 输入：nums = [7,8,9,11,12]
# 输出：1
# 解释：最小的正数 1 没有出现。 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= nums.length <= 10⁵ 
#  -2³¹ <= nums[i] <= 2³¹ - 1 
#  
# 
#  Related Topics 数组 哈希表 👍 2239 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        s= set(nums)
        """
        为什么只用遍历到len(nums)+1?
        因为我们关注的问题是：没有出现的 最小 正整数,假如数组长度为3
        那么最大的没有出现的最小整数只有一种情况就是 [1,2,3],即len(nums)+1
        虽然说-2**31 <= nums[i] <= 2**31 - 1,但是要求最小的正整数，正字排除了负数部分，
        最下又让我们不用关注大于数组长度+1的部分
        """
        for num in range(1,len(nums)+2):
            # set查找元素的时间复杂度为O(1)
            if num not in s:
                return num


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().firstMissingPositive(nums = [3,4,-1,1]))